package 题目集.动态规划.最大累加和;


/**
 * 前缀和思路{@link 题目集.前缀和.最大子数组和}
 * https://leetcode.cn/problems/maximum-subarray/description/
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组是数组中的一个连续部分。
 */
public class ch01_最大子数组和_dp {
    /**
     * 动态规划思路：
     *  状态表示：num[0...i]，0-i的所有子数组集合
     *  要求的值：所有子数组中最大的一个，max{num[0...i]}
     *  拆分集合：
     *      1.不要num[i]，num[0...i-1]的最大值。i>0。//错误，因为子数组必须是连续的，这样会导致num[0...i+1]不连续
     *      2.要num[i]，num[0...i-1]的最大值+num[i]，i>0
     *      3.只要num[i]，不要num[0...i-1]。i>0
     *  取最大值即可
     */
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int res = dp[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    /**
     * 状压
     */
    public int maxSubArray2(int[] nums) {
        int n = nums.length;
        int dp = nums[0];
        int res = dp;
        for (int i = 1; i < n; i++) {
            dp = Math.max(nums[i], dp + nums[i]);
            res = Math.max(res, dp);
        }
        return res;
    }

}
